{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.12-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python3",
   "display_name": "Python 3",
   "language": "python"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "source": [
    "# C09. 魔法方法\n",
    "\n",
    "-   构造函数：`__init__`，对象被构造时调用\n",
    "-   析构函数：`__del__`，对象被销毁时(作为垃圾被收集)前被调用，因为垃圾收集时间由系统决定，因此函数的行为不可预知，建议尽量不使用这个函数。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 9.1 Python 2\n",
    "\n",
    "Python 3 不需要显式地继承 object 或者 将 `__metaclass__` 设置为 type。所有的类都将隐式地继承 object。如果没有指定超类，将直接继承它，否则将间接地继承它。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 9.2 构造函数\n",
    "\n",
    "构造函数 `__init__` 将在对象创建后自动被调用。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "42\nThis is a constructor argument.\n"
     ]
    }
   ],
   "source": [
    "class FooBar:\n",
    "    def __init__(self, value=42):\n",
    "        self.somevar=value\n",
    "\n",
    "f1=FooBar()\n",
    "print(f1.somevar)\n",
    "\n",
    "f2=FooBar(\"This is a constructor argument.\")\n",
    "print(f2.somevar)"
   ]
  },
  {
   "source": [
    "### 9.2.1 重写函数"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Hello, I'm A.\nHello, I'm A.\n"
     ]
    }
   ],
   "source": [
    "class A:\n",
    "    def hello(self):\n",
    "        print(\"Hello, I'm A.\")\n",
    "class B(A):\n",
    "    pass\n",
    "\n",
    "a=A()\n",
    "b=B()\n",
    "a.hello()\n",
    "b.hello()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Hello, I'm B.\n"
     ]
    }
   ],
   "source": [
    "class B(A):\n",
    "    def hello(self):\n",
    "        print(\"Hello, I'm B.\")\n",
    "b=B()\n",
    "b.hello()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Aaaah...\nNo, thks!\n"
     ]
    }
   ],
   "source": [
    "class Bird:\n",
    "    def __init__(self):\n",
    "        self.hungry=True\n",
    "    def eat(self):\n",
    "        if self.hungry:\n",
    "            print(\"Aaaah...\")\n",
    "            self.hungry=False\n",
    "        else:\n",
    "            print(\"No, thks!\")\n",
    "b=Bird()\n",
    "b.eat()\n",
    "b.eat()            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Squawk!\n"
     ]
    }
   ],
   "source": [
    "class SongBird(Bird):\n",
    "    def __init__(self):\n",
    "        self.sound='Squawk!'\n",
    "    def sing(self):\n",
    "        print(self.sound)\n",
    "\n",
    "sb=SongBird()\n",
    "sb.sing()\n",
    "# sb.eat()  # 构造函数重写后，未调用超类的构造函数，导致超类的属性未被定义"
   ]
  },
  {
   "source": [
    "### 9.2.2 调用超类的构造函数：通过类名调用"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Squawk!\nAaaah...\n"
     ]
    }
   ],
   "source": [
    "class SongBird(Bird):\n",
    "    def __init__(self):\n",
    "        Bird.__init__(self)\n",
    "        self.sound='Squawk!'\n",
    "    def sing(self):\n",
    "        print(self.sound)\n",
    "\n",
    "sb=SongBird()\n",
    "sb.sing()\n",
    "sb.eat()"
   ]
  },
  {
   "source": [
    "### 9.2.3 调用超类的构造函数：通过 super 函数\n",
    "\n",
    "super 函数：可以自动寻找子类的父类，避免硬绑定。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "Squawk!\nAaaah...\nNo, thks!\n"
     ]
    }
   ],
   "source": [
    "class SongBird(Bird):\n",
    "    def __init__(self):\n",
    "        super().__init__()\n",
    "        self.sound='Squawk!'\n",
    "    def sing(self):\n",
    "        print(self.sound)\n",
    "\n",
    "sb=SongBird()\n",
    "sb.sing()\n",
    "sb.eat()\n",
    "sb.eat()"
   ]
  },
  {
   "source": [
    "## 9.3 元素访问\n",
    "\n",
    "协议：指的是规范行为的规则，类似于接口。协议指定应该实现哪些方法以及这些方法应该做些什么。在 Python 中，多态仅仅基于对象的行为，而不像其他语言那样要求对象基于特定的类或者实现特定的接口。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.3.1 基本协议：序列和映射\n",
    "\n",
    "序列和映射都是元素的集合，要实现它们的基本协议，不可变对象需要实现 2 个方法，可变对象需要实现 4 个方法。\n",
    "-   `__len__(self)`：返回集合包含的项数，序列即元素个数，映射即键-值对的数目。如果返回零，对象在布尔上下文中将被视为假(就像空的列表、元组、字符-   串、字典)。\n",
    "-   `__getitem__(self,key)`：返回与指定键相关联的值，序列中键为0到(n-1)的整数，n为序列的长度；映射中键可以为任何类型。\n",
    "-   `__setitem__(self,key,value)`：通过与键相关联的方式存储值，满足 `__getitem__` 来获取。仅用于可变对象\n",
    "-   `__delitem__(self,key)`：在对对象的组成部分使用 `__del__` 语句时被调用，删除与键相关联的值。仅用于可变对象\n",
    "\n",
    "说明：\n",
    "-   对于序列，如果键为负整数，则从尾往前数\n",
    "-   如果键的类型不合适，可能引发 TypeError 异常\n",
    "-   对于序列，如果索引的类型是正确的，但是超出了允许的范围，将引发 IndexError 异常"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "9\n2\n11\n"
     ]
    }
   ],
   "source": [
    "# 创建无穷序列\n",
    "def check_index(key):\n",
    "    if not isinstance(key,int):raise TypeError\n",
    "    if key<0:raise IndexError\n",
    "\n",
    "class ArithmeticSequence:\n",
    "    def __init__(self,start=0,step=1):\n",
    "        self.start=start\n",
    "        self.step=step\n",
    "        self.changed={}\n",
    "    def __getitem__(self,key):\n",
    "        check_index(key)\n",
    "        try: return self.changed[key]\n",
    "        except KeyError:\n",
    "            return self.start+key*self.step\n",
    "    def __setitem__(self,key,value):\n",
    "        check_index(key)\n",
    "        self.changed[key]=value\n",
    "\n",
    "s=ArithmeticSequence(1,2)\n",
    "print(s[4])\n",
    "s[4]=2\n",
    "print(s[4])\n",
    "print(s[5])\n",
    "# del s[4]  # 没有实现 __delitem__ 函数，禁止删除元素\n",
    "# print(s['four'])  # 错误的索引类型\n",
    "# print(s[-5])      # 错误的索引位置"
   ]
  },
  {
   "source": [
    "### 9.3.2 从系统的序列类(list, dict, str)中派生"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "c1= [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]\nc1= [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]\nc1= [9, 8, 7, 3, 2, 1, 0]\nc1.counter= 0\nc1[4]+c1[2]= 9\nc1.counter= 2\n"
     ]
    }
   ],
   "source": [
    "# 带访问计数器的列表\n",
    "class CounterList(list):\n",
    "    def __init__(self,*args):\n",
    "        super().__init__(*args)\n",
    "        self.counter=0\n",
    "    def __getitem__(self,index):\n",
    "        self.counter+=1\n",
    "        return super(CounterList,self).__getitem__(index)\n",
    "\n",
    "c1=CounterList(range(10))\n",
    "print(\"c1=\",c1)\n",
    "c1.reverse()\n",
    "print(\"c1=\",c1)\n",
    "del c1[3:6]\n",
    "print(\"c1=\",c1)\n",
    "# c1.__getitem__ 被调用的次数\n",
    "print(\"c1.counter=\",c1.counter)\n",
    "print(\"c1[4]+c1[2]=\",c1[4]+c1[2])\n",
    "print(\"c1.counter=\",c1.counter)"
   ]
  },
  {
   "source": [
    "## 9.4 其他的魔法方法\n",
    "\n",
    "参阅《Python Reference Manaul》中的「Special method names」节。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "## 9.5 特性"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "r.get_size()= (10, 5)\nr.width= 150\n"
     ]
    }
   ],
   "source": [
    "class Rectangle:\n",
    "    def __init__(self):\n",
    "        self.width=0\n",
    "        self.height=0\n",
    "    def set_size(self, size):\n",
    "        self.width, self.height=size\n",
    "    def get_size(self):\n",
    "        return self.width, self.height\n",
    "\n",
    "r=Rectangle()\n",
    "r.width=10\n",
    "r.height=5\n",
    "print(\"r.get_size()=\",r.get_size())\n",
    "r.set_size((150,100))\n",
    "print(\"r.width=\",r.width)"
   ]
  },
  {
   "source": [
    "### 9.5.1 property 函数\n",
    "\n",
    "通过存取方法定义的属性通常称为特征(property)。\n",
    "\n",
    "说明：property 本质不是函数，而是一个类。它的实例包含一些魔法方法(__get__, __set__, __delete__)，这些魔法方法定义了所谓的描述符协议。只要对象实现了这些方法中的任何一个，它就是一个描述符。\n",
    "\n",
    "描述符的说明参考 [Descriptor HowTo Guide](https://docs.python.org/3/howto/descriptor.html)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "r.size= (10, 5)\nr.width= 150\n"
     ]
    }
   ],
   "source": [
    "class Rectangle:\n",
    "    def __init__(self):\n",
    "        self.width=0\n",
    "        self.height=0\n",
    "    def set_size(self, size):\n",
    "        self.width, self.height=size\n",
    "    def get_size(self):\n",
    "        return self.width, self.height\n",
    "    size=property(get_size,set_size)\n",
    "\n",
    "r=Rectangle()\n",
    "r.width=10\n",
    "r.height=5\n",
    "print(\"r.size=\",r.size)\n",
    "r.size=150,100\n",
    "print(\"r.width=\",r.width)"
   ]
  },
  {
   "source": [
    "### 9.5.2 静态方法 与 类方法\n",
    "\n",
    "静态方法的定义中没有参数 self，可以直接通过类来调用。\n",
    "类方法的定义中包含参数 self，可以通过类调用，也可以通过对象调用。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "This is a static method!\nThis is a class method!\nThis is a class method!\n"
     ]
    }
   ],
   "source": [
    "class MyClass:\n",
    "    @staticmethod\n",
    "    def smeth():\n",
    "        print(\"This is a static method!\")\n",
    "    \n",
    "    @classmethod\n",
    "    def cmeth(cls):\n",
    "        print(\"This is a class method!\")\n",
    "\n",
    "MyClass.smeth()\n",
    "MyClass.cmeth()\n",
    "m=MyClass()\n",
    "m.cmeth()"
   ]
  },
  {
   "source": [
    "### 9.5.3 控制对象属性访问的魔法方法：`__getattr__`, `__setattr__`\n",
    "\n",
    "-   `__getattribute__(self,name)`：在属性被访问时自动调用\n",
    "-   `__getattr__(self,name)`：在属性被访问而对象没有这样的属性时自动调用\n",
    "-   `__setattr__(self,name,value)`：在给属性赋值时自动调用\n",
    "-   `__delattr__(self,name)`：在删除属性时自动调用"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "r.size= (10, 5)\nr.width= 150\n"
     ]
    }
   ],
   "source": [
    "class Rectangle:\n",
    "    def __init__(self):\n",
    "        self.width=0\n",
    "        self.height=0\n",
    "    def __setattr__(self,name,value):\n",
    "        if name=='size':\n",
    "            self.width,self.height=value\n",
    "        else:\n",
    "            # 使用 __dict__ 赋值，而不直接赋值是避免出现再次调用 __setattr__，导致无限循环\n",
    "            # 使用 __dict__ 赋值时，也要避免 __getattribute__ 拦截所有访问导致无限循环，\n",
    "            self.__dict__[name]=value\n",
    "    def __getattr__(self,name):\n",
    "        if name=='size':\n",
    "            return self.width,self.height\n",
    "        else:\n",
    "            raise AttributeError()\n",
    "\n",
    "r=Rectangle()\n",
    "r.width=10\n",
    "r.height=5\n",
    "print(\"r.size=\",r.size)\n",
    "r.size=150,100\n",
    "print(\"r.width=\",r.width)        \n"
   ]
  },
  {
   "source": [
    "## 9.6 迭代器"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.6.1 迭代器协议\n",
    "\n",
    "迭代(iter)：意味着重复多次，就像循环一样。\n",
    "\n",
    "注意：实现了 `__iter__` 的对象是可迭代的，实现了 `__next__` 的对象是迭代器，方法 `__iter__` 返回迭代器。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1597\n"
     ]
    }
   ],
   "source": [
    "class Fibs:\n",
    "    def __init__(self):\n",
    "        self.a=0\n",
    "        self.b=1\n",
    "    def __next__(self):\n",
    "        self.a, self.b=self.b,self.a+self.b\n",
    "        return self.a\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "fibs=Fibs()\n",
    "for f in fibs:\n",
    "    if f>1000:\n",
    "        print(f)\n",
    "        break"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1\n5\n7\n1\n5\n7\n"
     ]
    }
   ],
   "source": [
    "# 使用内置函数 `iter` 也可以获得迭代器\n",
    "for i in [1,5,7]:\n",
    "    print(i)\n",
    "\n",
    "for it in iter([1,5,7]):\n",
    "    print(it)"
   ]
  },
  {
   "source": [
    "### 9.6.2 基于迭代器创建序列"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]"
      ]
     },
     "metadata": {},
     "execution_count": 13
    }
   ],
   "source": [
    "class TestIterator:\n",
    "    value=0\n",
    "    def __next__(self):\n",
    "        self.value+=1\n",
    "        if self.value>10:raise StopIteration\n",
    "        return self.value\n",
    "    def __iter__(self):\n",
    "        return self\n",
    "\n",
    "ti=TestIterator()\n",
    "list(ti)"
   ]
  },
  {
   "source": [
    "## 9.7 生成器\n",
    "\n",
    "生成器是使用普通函数语法定义的迭代器"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.7.1 创建生成器"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "1\n2\n3\n4\n5\n"
     ]
    }
   ],
   "source": [
    "# 包含 yield 语句的函数都被称为生成器\n",
    "# 每次使用 yield 生成一个值后，函数都将被冻结，并在此等待被重新唤醒，唤醒后继续执行\n",
    "def flatten(nested):\n",
    "    for sublist in nested:\n",
    "        for element in sublist:\n",
    "            yield element\n",
    "\n",
    "nested=[[1,2],[3,4],[5]]\n",
    "for num in flatten(nested):\n",
    "    print(num)"
   ]
  },
  {
   "source": [
    "### 9.7.2 递归式生成器\n",
    "\n",
    "调用 flatten 时，有两种可能性：基线条件 和 递归条件。\n",
    "在基线条件下，要求这个函数展开单个元素(例如一个数)"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n[1]\n"
     ]
    }
   ],
   "source": [
    "def flatten(nested):\n",
    "    try:\n",
    "        for sublist in nested:\n",
    "            for element in flatten(sublist):\n",
    "                yield element\n",
    "    except TypeError:\n",
    "        yield nested\n",
    "\n",
    "print(list(flatten([[[1],2],3,4,[5,[6,7]],8])))\n",
    "\n",
    "print(list(flatten(1)))\n",
    "\n",
    "# 对字符串迭代会导致无穷递归，因为字符串的第一个元素是一个长度为 1 的字符串，而长度为 1 的字符串的第一个元素就是字符串本身\n",
    "# print(list(flatten(['foo',['bar',['baz']]])))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "['foo', 'bar', 'baz']\n"
     ]
    }
   ],
   "source": [
    "def flatten(nested):\n",
    "    try:\n",
    "        # 如果是字符串对象，直接抛出 TypeError 从而避免迭代\n",
    "        try: nested+''\n",
    "        except TypeError: pass\n",
    "        else: raise TypeError\n",
    "        \n",
    "        for sublist in nested:\n",
    "            for element in flatten(sublist):\n",
    "                yield element\n",
    "    except TypeError: yield nested\n",
    "\n",
    "print(list(flatten(['foo',['bar',['baz']]])))"
   ]
  },
  {
   "source": [
    "### 9.7.3 通用的生成器\n",
    "\n",
    "生成器的函数 和 生成器的迭代器 通称为 生成器。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "<function simple_generator at 0x00000000079156A8>\n<generator object simple_generator at 0x000000000953EDB0>\ni= 1\n"
     ]
    }
   ],
   "source": [
    "def simple_generator():\n",
    "    yield 1\n",
    "\n",
    "print(simple_generator)\n",
    "print(simple_generator())\n",
    "for i in simple_generator():\n",
    "    print(\"i=\",i)"
   ]
  },
  {
   "source": [
    "### 9.7.4 生成器的方法\n",
    "\n",
    "-   外部世界：可以访问生成器的方法 send，类似于 next，但是要接受一个参数(值为需要发送的「消息」，「消息」可以是任何对象)\n",
    "-   生成器：在挂起的生成器内部， yield 可能用作表达式而不是语句。当生成器重新运行时，yield  返回一个值——通过 send 从外部世界发送的值。如果使用的是 next，yield 返回 None。\n",
    "    -   throw 方法：用于在生成器中(yield 表达式处) 引发异常，调用时可以提供一个异常类型、一个可选值、一个 traceback 对象\n",
    "    -   close 方法：用于停止生成器，调用时无需提供任何参数"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "42\n42\nHello, world!\n"
     ]
    }
   ],
   "source": [
    "def repeater(value):\n",
    "    while True:\n",
    "        new=(yield value)\n",
    "        if new is not None: value=new\n",
    "r=repeater(42)\n",
    "print(next(r))\n",
    "print(next(r))\n",
    "print(r.send(\"Hello, world!\"))        "
   ]
  },
  {
   "source": [
    "### 9.7.5 模拟生成器"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[1, 2, 3, 4, 5, 6, 7, 8]\n[1]\n['foo', 'bar', 'baz']\n"
     ]
    }
   ],
   "source": [
    "# 使用普通函数模拟生成器\n",
    "def flatten(nested):\n",
    "    result=[]\n",
    "    try:\n",
    "        try: nested+''\n",
    "        except TypeError: pass\n",
    "        else: raise TypeError\n",
    "        \n",
    "        for sublist in nested:\n",
    "            for element in flatten(sublist):\n",
    "                result.append(element)\n",
    "    except TypeError: result.append(nested)\n",
    "    return result\n",
    "\n",
    "print(list(flatten([[[1],2],3,4,[5,[6,7]],8])))\n",
    "print(list(flatten(1)))\n",
    "print(list(flatten(['foo',['bar',['baz']]])))"
   ]
  },
  {
   "source": [
    "## 9.8 经典问题：八皇后问题"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.8.1 生成器回溯\n",
    "\n",
    "-   不使用生成器时，算法需要通过额外的参数来传递部分结果，从而让递归能够接着往下计算。\n",
    "-   使用生成器时，所有的递归调用都只需要生成其负责部分的结果，这种策略可以用来遍历图结构和树结构。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.8.2 问题描述\n",
    "\n",
    "将 8 个皇后放在棋盘上，要求是任何一个皇后都不能威胁到其他皇后，即任何两个皇后都不能吃掉对方。\n",
    "\n",
    "这是一个典型的回溯问题：在棋盘的第一行尝试为第一个皇后选择一个位置，再在第二行尝试为第二个皇后选择一个位置，依次类推至无法为当前皇后找到合适位置时，就回溯到前一个皇后，并尝试为它选择另一个位置。最后，要么深度完成所有可能而失败，要么找到正确的答案。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.8.3 状态表示\n",
    "\n",
    "`state[0]=3`：表示第 1 行的皇后放在第 4 列。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "source": [
    "### 9.8.4 检测冲突\n",
    "\n",
    "要找出没有冲突的位置组合，首先定义冲突是什么？"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def conflict(state, nextX):\n",
    "    nextY=len(state)\n",
    "    for i in range(nextY):\n",
    "        if abs(state[i]-nextX) in (0,nextY-i):\n",
    "            # 如果下一个皇后与当前皇后的 x 坐标相同，则发生冲突\n",
    "            # 如果下一个皇后与当前皇后在左对角线(负值)或者右对角线(正值)时，则发生冲突\n",
    "            return True"
   ]
  },
  {
   "source": [
    "### 9.8.5基线条件\n"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      "[0]\n[2]\n[4]\n[]\n"
     ]
    }
   ],
   "source": [
    "def queens(num,state):\n",
    "    if len(state)==num-1:\n",
    "        for pos in range(num):\n",
    "            if not conflict(state,pos):\n",
    "                yield pos\n",
    "print(list(queens(3,(1,3))))\n",
    "print(list(queens(4,(1,3,0))))\n",
    "print(list(queens(5,(1,3,0,2))))\n",
    "print(list(queens(6,(1,3,0,2,4))))"
   ]
  },
  {
   "source": [
    "### 9.8.6 递归条件"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def queens(num=8, state=()):\n",
    "    for pos in range(num):\n",
    "        if not conflict(state,pos):\n",
    "            if len(state)==num-1:\n",
    "                # 返回的序列长度与棋盘大小一样时\n",
    "                yield(pos,)\n",
    "            else:\n",
    "                for result in queens(num, state+(pos,)):\n",
    "                    yield (pos,)+result"
   ]
  },
  {
   "source": [
    "### 9.8.7 扫尾工作"
   ],
   "cell_type": "markdown",
   "metadata": {}
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pretty_print(solution):\n",
    "    def line(pos, length=len(solution)):\n",
    "        return '. '*(pos)+'X '+'. '*(length-pos-1)\n",
    "    for pos in solution:\n",
    "        print(line(pos))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": [
      ". X . . . . . . \n. . . . X . . . \n. . . . . . X . \nX . . . . . . . \n. . X . . . . . \n. . . . . . . X \n. . . . . X . . \n. . . X . . . . \n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "pretty_print(random.choice(list(queens())))"
   ]
  },
  {
   "source": [
    "## 9.9小结\n",
    "\n",
    "-   新式类 和 旧式类：Python 2.2 开始引入新式类\n",
    "-   魔法方法：Python 的特殊方法，名称以两个下划线开头和结尾。这些方法的功能各不相同，但是大都由 Python 在特定的情况下自动调用。\n",
    "-   构造函数：对象创建后自动调用 `__init__`\n",
    "-   重写：子类可以重写超类中的方法(以及其他任何属性)。调用被重写的超类方法，可以通过超类直接调用，也可以通过函数 `super` 调用\n",
    "-   序列 和 映射：创建自定义的序列或者映射，可以实现序列或者映射指定的所有方法；也可以从 list 或者 dict 派生\n",
    "-   迭代器：包含方法 `__next__` 的对象，可以用于迭代一组值。没有更多的值可供迭代时，方法将会引发 `StopIteration` 异常。可迭代的对象包含方法 `__iter__`，这个方法返回一个像序列一样可以用于 for 循环中的迭代器。\n",
    "-   生成器：生成器的函数包含关键字 yield，函数在被调用时返回一个生成器，即一种特殊的迭代器。使用方法 `send`、`throw`、`close` 可以与活动的生成器交互。\n",
    "-   八皇后问题：：著名的计算机科学问题，使用生成器解决它。"
   ],
   "cell_type": "markdown",
   "metadata": {}
  }
 ]
}